package leetcode.offer_two_special.queue;

import leetcode.tree.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author mazouri
 * @create 2021-09-11 19:32
 */
public class _44_largestValues {
    public List<Integer> largestValues1(TreeNode root) {
        int current = 0;
        int next = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
            current = 1;
        }

        ArrayList<Integer> res = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            current--;
            max = Math.max(max, node.val);

            if (node.left != null) {
                queue.offer(node.left);
                next++;
            }

            if (node.right != null) {
                queue.offer(node.right);
                next++;
            }

            if (current == 0) {
                res.add(max);
                max = Integer.MIN_VALUE;
                current = next;
                next = 0;
            }
        }
        return res;
    }

    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        if (root != null) q1.offer(root);

        ArrayList<Integer> res = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        while (!q1.isEmpty()) {
            TreeNode node = q1.poll();
            max = Math.max(max, node.val);

            if (node.left != null) q1.offer(node.left);
            if (node.right != null) q1.offer(node.right);

            if (q1.isEmpty()) {
                res.add(max);
                max = Integer.MIN_VALUE;
                q1 = q2;
                q2 = new LinkedList<>();
            }
        }
        return res;
    }
}
